其他
苏炳添很快,计数排序也很快,比快速排序还快
The following article is from 爱码有道 Author 点击关注👉👉
作者:道哥
来源:经授权转自公众号 爱码有道(ID:aimayoudao)
图解计数排序
接下来,我们定义一个计数器,遍历上述每个考生,分别统计每个分数值有多少人:
所以,计数排序后的结果就是:
这便是计数排序的过程,时间复杂度为O(n),整个过程中没有任何比较大小的操作,只有计数操作。
计数排序的思路看似简单,但很多面试者在现场是没法想到这种思路的,除非提前了解过计数排序。
计数排序代码
接下来,我们根据上述思路,来写一下计数排序的C++代码:
#include<iostream>
using namespace std;
void countSort(int a[], int n, int k)
{
int *countArray = new int[k + 1];
int *finalArray = new int[n];
int i = 0;
for(i = 0; i <= k; i++)
{
countArray[i] = 0;
}
for(i = 0; i < n; i++)
{
countArray[a[i]]++;
}
for(i = 1; i <= k; i++)
{
countArray[i] += countArray[i - 1];
}
for(i = 0; i < n; i++)
{
finalArray[--countArray[a[i]]] = a[i];
}
for(i = 0; i < n; i++)
{
a[i] = finalArray[i];
}
delete [] finalArray;
delete [] countArray;
}
int main()
{
int a[] = {2, 1, 2, 3, 0};
int n = sizeof(a) / sizeof(a[0]);
int maxPossibleScore = 3;
countSort(a, n, maxPossibleScore);
int i = 0;
for(i = 0; i < n; i++)
{
cout << a[i] << " ";
}
cout << endl;
return 0;
}
结果:0 1 2 2 3
也即:
点分享
点点赞
点在看